package bTree;

import java.lang.reflect.Field;
import java.util.Arrays;

public class bTree {
    //节点类包含5个属性
    public class Node {
        int[] key;
        Node[] children;
        int keynumber;//有效的key数
        boolean isLeaf;
        int t;//最小度,最小孩子数
        final int MAX_KEYNUMBER = 2 * t - 1;
        final int MIN_KEYNNUMBER = t - 1;


        Node root;//初始化一个root

        public Node() {
            t = 2;//默认约定t最小等于2
        }

        //要有一个给t赋值的构造方法
        public Node(int t) {
            this.t = t;
            this.children = new Node[2 * t];//约定最大孩子数是最小度的两倍
            this.key = new int[MAX_KEYNUMBER];
        }

        //重写tostring方法,打印应该是打印到有效长度
        public String toString() {
            return Arrays.toString(Arrays.copyOfRange(key, 0, keynumber - 1));
        }

        //查找方法
        Node get(int key) {
            //定义i来查看退出循环时是第几个
            int i = 0;
            while (i < keynumber) {
                if (this.key[i] == key) {
                    return this;
                } else if (this.key[i] > key) {
                    break;
                }
                i++;
            }
            //如果该节点已经是叶子节点了，没找到，返回null，否则递归查找
            if (isLeaf) {
                return null;
            }
            return children[i].get(key);
        }

        //按位置插入key
        void insertkey(int key, int index) {
            for (int i = keynumber - 1; i >= index; i--) {
                this.key[i + 1] = this.key[i];
            }
            this.key[index] = key;
            //别忘记keynumber++
            keynumber++;
        }

        //按索引插入孩子
        void insertchild(Node child, int index) {
            for (int i = keynumber - 1; i >= index; i--) {
                this.children[i + 1] = this.children[i];
            }
            this.children[index] = child;
            //别忘记keynumber++
            keynumber++;
        }

        //是否包含，contains方法,判断是否包含某个key
        boolean contains(int key) {
            return root.get(key) != null;
        }

        //添加方法put
        void put(int key) {
            //因为需要递归，传的参数不一样，所以另外=写一个递归函数来调用
            doput(root, key);
        }

        //doput函数
        void doput(Node n, int key) {
            int i = 0;//标记退出时在该节点的索引
            while (i < n.keynumber) {
                if (n.key[i] == key) {
                    //走更新操作，并返回
                    return;
                }
                if (n.key[i] > key) {
                    //过头了，应该退出去
                    break;//找到插入位置
                }
                i++;
                // 到下一步，如果是叶子节点直接加，否则继续递归
            }
                if (n.isLeaf) {
                    n.insertkey(key, i);
                } else {
                    doput(n.children[i], key);
                }

        }

        //分裂方法split
        void split(Node parent,Node left,int index){//index是原来待分裂节点所在索引
            //第一步判断分裂节点是否为根节点
            if(parent==null){
                //需要增多两个节点，其中一个是新根节点
                Node newRoot=new Node(t);
                newRoot.isLeaf=false;//设置false；
                newRoot.insertchild(left,0);//把原节点插入当作新节点孩子
                this.root=newRoot;//更新root
                parent=newRoot;
            }

            //接着是具体的实现
            Node right=new Node(t);
            right.isLeaf=left.isLeaf;//创建后的更新
            //还需判断left有没有孩子，如果有，需要先处理孩子
            if(!left.isLeaf){
                System.arraycopy(left.children,t,right.children,0,t);
                //我觉得黑马少了一步，应该把left后面的都去掉才对
            }
            //把大的一部分key复制给right
            System.arraycopy(left.key,t,right.key,0,t-1);
            //把中间的挂到父节点去
            int mid=left.key[t-1];
            parent.insertkey(mid,index);//
            //再把right挂到父节点的index+1孩子处
            parent.insertchild(right,index+1);
            //我觉得黑马少了一步，应该把left后面的都去掉才对

            //注意更新keynumber,left和right都为t-1
            left.keynumber=t-1;
            right.keynumber=t-1;

        }

    }
}
